#include<bits/stdc++.h>
using namespace std;
const int NN=1004;
string s[NN];
int main()
{
	freopen("brotherhood.in","r",stdin);
	freopen("brotherhood.out","w",stdout);
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n,t;
	cin>>n>>t;
	s[1]="0",s[2]="1";
	for(int i=3;i<=n;i++)
		s[i]=s[i-1]+s[i-2];
	while(t--)
	{
		string x;
		cin>>x;
		int ans=0;
		for(int i=0;i<=s[n].size()-x.size();i++)
			if(s[n].substr(i,x.size())==x)
				ans++;
		cout<<ans<<'\n';
	}
	return 0;
}
